个子|都会_LeetCode0427「建立四叉树」

篇首语：本文由编程笔记#小编为大家整理，主要介绍了LeetCode 0427「建立四叉树」相关的知识，希望对你有一定的参考价值。

文章目录

• • 题目
  • 分析
  • 实现
  
  

题目

给你一个 n * n 矩阵 grid&＃xff0c;矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid。

你需要返回能表示矩阵的四叉树的根结点。

注意&＃xff0c;当 isLeaf 为 False 时&＃xff0c;你可以把 True 或者 False 赋值给节点&＃xff0c;两种值都会被判题机制 接受 。四叉树数据结构中&＃xff0c;每个内部节点只有四个子节点。此外&＃xff0c;每个节点都有两个属性&＃xff1a;

• val&＃xff1a;储存叶子结点所代表的区域的值。1 对应 True&＃xff0c;0 对应 False&＃xff1b;
• isLeaf: 当这个节点是一个叶子结点时为 True&＃xff0c;如果它有 4 个子节点则为 False 。

class Node
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;



我们可以按以下步骤为二维区域构建四叉树&＃xff1a;

1. 如果当前网格的值相同&＃xff08;即&＃xff0c;全为 0 或者全为 1&＃xff09;&＃xff0c;将 isLeaf 设为 True &＃xff0c;将 val 设为网格相应的值&＃xff0c;并将四个子节点都设为 Null 然后停止。
2. 如果当前网格的值不同&＃xff0c;将 isLeaf 设为 False&＃xff0c; 将 val 设为任意值&＃xff0c;然后如下图所示&＃xff0c;将当前网格划分为四个子网格。
3. 使用适当的子网格递归每个子节点。

四叉树格式&＃xff1a;

• 输出为使用层序遍历后四叉树的序列化形式&＃xff0c;其中 null 表示路径终止符&＃xff0c;其下面不存在节点。
• 它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。
• 如果 isLeaf 或者 val 的值为 True &＃xff0c;则表示它在列表 [isLeaf, val] 中的值为 1 &＃xff1b;如果 isLeaf 或者 val 的值为 False &＃xff0c;则表示值为 0 。

示例1&＃xff1a;

• 输入&＃xff1a;grid &＃61; [[0,1],[1,0]]
• 输出&＃xff1a;[[0,1],[1,0],[1,1],[1,1],[1,0]]
• 解释&＃xff1a;此示例的解释如下&＃xff1a;请注意&＃xff0c;在下面四叉树的图示中&＃xff0c;0 表示 false&＃xff0c;1 表示 True 。

示例2&＃xff1a;

• 输入&＃xff1a;grid &＃61; [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
• 输出&＃xff1a;[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
• 解释&＃xff1a;网格中的所有值都不相同。我们将网格划分为四个子网格。topLeft&＃xff0c;bottomLeft 和 bottomRight 均具有相同的值。topRight 具有不同的值&＃xff0c;因此我们将其再分为 4 个子网格&＃xff0c;这样每个子网格都具有相同的值。

提示&＃xff1a;

• n &＃61;&＃61; grid.length &＃61;&＃61; grid[i].length
• n &＃61;&＃61; 2^x 其中 0 <&＃61; x <&＃61; 6

题目来源&＃xff1a;LeetCode

分析

此题可以采用递归的方式。定义一个递归函数&＃xff0c;传入一个区域范围的网格&＃xff0c;函数返回此区域范围网格的根节点。

一开始传入递归函数的是整个原始的网格&＃xff0c;在递归函数中&＃xff0c;如果判断要此范围的网格的所有单元格值都相同&＃xff0c;那么返回叶子节点&＃xff0c;递归结束。否则&＃xff0c;将此范围网格划分四个小区域网格&＃xff0c;然后构建一个带有4个子节点的节点对象返回&＃xff0c;子节点依旧调用递归函数计算而来。

实现

package com.chenpi.no0427Construct;
/**
* &＃64;author 陈皮
* &＃64;version 1.0
* &＃64;description
* &＃64;date 2022/4/29
*/
public class No0427Construct
public static void main(String[] args)
No0427Construct inst &＃61; new No0427Construct();
int[][] grid &＃61; 0, 1, 1, 0;
Node rootNode &＃61; inst.construct(grid);
System.out.println(rootNode);

public Node construct(int[][] grid)
// 返回整个大网格的根节点
return dfs(grid, 0, grid.length, 0, grid.length);

public Node dfs(int[][] grid, int beginRow, int endRow, int beginCol, int endCol)
// 判断此区域的网格的所有节点值是否相同
boolean same &＃61; true;
for (int i &＃61; beginRow; i < endRow; i&＃43;&＃43;)
for (int j &＃61; beginCol; j < endCol; j&＃43;&＃43;)
// 直接拿此区域的第一个节点与其他节点比较即可
if (grid[beginRow][beginCol] !&＃61; grid[i][j])
same &＃61; false;
break;


if (!same)
break;


// 如果所有节点相同&＃xff0c;则是叶子节点
if (same)
// 叶子节点的值和此区域网格的值相同
return new Node(grid[beginRow][beginCol] &＃61;&＃61; 1, true);

// 不是叶子节点,则构建一个带有4个子节点的节点
return new Node(
true,
false,
dfs(grid, beginRow, (beginRow &＃43; endRow) / 2, beginCol, (beginCol &＃43; endCol) / 2),
dfs(grid, beginRow, (beginRow &＃43; endRow) / 2, (beginCol &＃43; endCol) / 2, endCol),
dfs(grid, (beginRow &＃43; endRow) / 2, endRow, beginCol, (beginCol &＃43; endCol) / 2),
dfs(grid, (beginRow &＃43; endRow) / 2, endRow, (beginCol &＃43; endCol) / 2, endCol)
);


/**
* 四叉树节点
*/
class Node
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
public Node()
this.val &＃61; false;
this.isLeaf &＃61; false;
this.topLeft &＃61; null;
this.topRight &＃61; null;
this.bottomLeft &＃61; null;
this.bottomRight &＃61; null;

public Node(boolean val, boolean isLeaf)
this.val &＃61; val;
this.isLeaf &＃61; isLeaf;
this.topLeft &＃61; null;
this.topRight &＃61; null;
this.bottomLeft &＃61; null;
this.bottomRight &＃61; null;

public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft,
Node bottomRight)
this.val &＃61; val;
this.isLeaf &＃61; isLeaf;
this.topLeft &＃61; topLeft;
this.topRight &＃61; topRight;
this.bottomLeft &＃61; bottomLeft;
this.bottomRight &＃61; bottomRight;

&＃64;Override
public String toString()
return "[" &＃43; (isLeaf ? 1 : 0) &＃43; "," &＃43; (val ? 1 : 0) &＃43; "]" &＃43; topLeft &＃43; topRight &＃43; bottomLeft
&＃43; bottomRight;




Leetcode 执行结果&＃xff1a;

本次分享到此结束啦~~

如果觉得文章对你有帮助&＃xff0c;点赞、收藏、关注、评论&＃xff0c;您的支持就是我创作最大的动力&＃xff01;